1. Field of the Invention
The invention pertains to a memory system having an array of flash memory cells and a controller (e.g., one embodiment is a flash memory system of this type which emulates a magnetic disk drive). Aspects of the invention are methods and apparatus which encode packets of data bits to be written to erased flash memory cells so as to reduce the average power and time needed to write the packets to the cells. In preferred embodiments, the invention generates a count indicative of how many bits of each packet would require programming of cells if the packet were written to the cells without being encoded, and encodes the packets according to the count (preferably by inverting the polarity of each packet for which the bit count exceeds a preset value).
2. Description of Related Art
It is conventional to implement a memory circuit as an integrated circuit which includes an array of flash memory cells and circuitry for independently erasing selected blocks of the cells and programming selected ones of the cells. FIG. 1 is a simplified block diagram of such an integrated circuit (flash memory chip 103). To enable such an integrated flash memory chip (or a memory system including such a memory chip) to implement the present invention, its controller (controller 29 of FIG. 1) would be replaced by a controller which implements the invention (including by encoding packets of data received from a host processor in accordance with the invention), and optionally also an appropriate host interface would be provided between the controller and circuitry external to the chip.
Memory chip 103 of FIG. 1 includes flash memory array circuit 16 (comprising rows and columns of nonvolatile flash memory cells), I/O pins DQ0-DQ15 (for asserting output data to an external device or receiving input data from an external device), input buffer circuits 122, 122A, and 122B, output buffer circuits 128, 128A, and 128B, address buffer 17 for receiving address bits A0 through A17 from an external device, row decoder circuit (X address decoder) 12, column multiplexer circuit (Y multiplexer) 14, and control unit 29 (also denoted herein as "controller" 29).
Each of the cells (storage locations) of memory array circuit 16 is indexed by a row index (an "X" index determined by decoder circuit 12) and a column index (a "Y" index determined by Y decoder circuit 13 of circuit 14). Each column of cells of memory array 16 comprises "n" memory cells, each cell implemented by a single floating-gate N-channel transistor. The drains of all transistors of a column are connected to a bitline, and the gate of each of the transistors is connected to a different wordline, and the sources of the transistors are held at a source potential (which is usually ground potential for the chip during a read or programming operation). Each memory cell is a nonvolatile memory cell since the transistor of each cell has a floating gate capable of semipermanent charge storage. The current drawn by each cell (i.e., by each of the N-channel transistors) depends on the amount of charge stored on the cell's floating gate. Thus, the charge stored on each floating gate determines a data value that is stored "semipermanently" in the corresponding cell. In cases in which each of the N-channel transistors is a flash memory device, the charge stored on the floating gate of each is erasable (and thus the data value stored by each cell is erasable) by appropriately changing the voltage applied to the gate and source (in a well known manner).
The individual memory cells (not depicted) are addressed by eighteen address bits (A0-A17), with nine bits being used by X decoder circuit 12 to select the row of array 16 in which the target cell (or cells) is (or are) located and the remaining nine bits being used by Y decoder circuit 13 (of Y-multiplexer 14) to select the appropriate column (or columns) of array 16. Typically, a set of eight or sixteen target cells (or 256 target cells) in a single row of the array are selected by a single set of eighteen address bits A0-A17, with Y decoder circuit 13 determining the column addresses of such cells in response to a nine-bit subset of the set of address bits. In response to the other nine address bits A0-A17, X decoder circuit 12 determines a row address which selects one cell in each selected column.
In a normal operating mode, chip 103 executes a write operation as follows. Address buffer 17 asserts appropriate ones of address bits A0-A17 to circuit 14 and decoder circuit 12. In response to these address bits, circuit 14 determines a column address (which selects one of the columns of memory cells of array 16), and circuit 12 determines a row address (which selects one cell in the selected column). In response to a write command supplied from controller 29, a signal (indicative of a bit of data) present at the output of input buffer 122, 122A, and/or 122B is asserted through circuit 14 to the cell of array 16 determined by the row and column address (e.g., to the drain of such cell). During such write operation, output buffers 128, 128A, and 128B are disabled. Depending on the value of the data bit, the cell is either programmed or it remains in an erased state.
In the normal operating mode, chip 103 executes a read operation as follows. Address buffer 17 asserts appropriate ones of address bits A0-A17 to circuit 14 and address decoder circuit 12. In response to these address bits, circuit 14 asserts a column address to memory array 16 (which selects one of the columns of memory cells), and circuit 12 asserts a row address to memory array 16 (which selects one cell in the selected column). In response to a read command supplied from control unit 29, a current signal indicative of a data value stored in the cell of array 16 (a "data signal") determined by the row and column address is supplied from the drain of the selected cell through the bitline of the selected cell and then through circuit 14 to sense amplifier circuitry 33. This data signal is processed in amplifier circuitry 33, buffered in output buffers 128, 128A, and/or 128B, and finally asserted at pins DQ0-DQ15. During such read operation, input buffers 122, 122A, and 122B are disabled.
Chip 103 also includes a pad which receives a high voltage V.sub.pp from an external device, and a switch 121 connected to this pad. During some steps of a typical erase or program sequence (in which cells of array 16 are erased or programmed), control unit 29 sends a control signal to switch 121 to cause switch 121 to close and thereby assert the high voltage V.sub.pp to various components of the chip including X decoder 12. Voltage V.sub.pp is higher (typically V.sub.pp =12 volts) than the normal operating mode supply voltage (typically V.sub.cc =5 volts or V.sub.cc =5.5 volts) for the MOS transistors of chip 103.
When reading a selected cell of array 16, if the cell is in an erased state, the cell will conduct a first current which is converted to a first voltage in sense amplifier circuitry 33. If the cell is in a programmed state, it will conduct a second current which is converted to a second voltage in sense amplifier circuitry 33. Sense amplifier circuitry 33 determines the state of the cell (i.e., whether it is programmed or erased corresponding to a binary value of 0 or 1, respectively) by comparing the voltage indicative of the cell state to a reference voltage. The outcome of this comparison is an output which is either high or low (corresponding to a digital value of one or zero) which sense amplifier circuitry 33 sends to output buffers 128 and 128B (and through multiplexer 124 to output buffer 128A). One or more of the output buffers in turn asserts a corresponding data signal to corresponding ones of pins DQ0-DQ15 (from which it can be accessed by an external device).
It is important during a write operation to provide the wordline of the selected cell with the proper voltage and the drain of the selected cell with the appropriate voltage level (the voltage determined by the output of each input buffer, asserted through latch/multiplexer 130' to circuit 14), in order to successfully write data to the cell without damaging the cell.
Internal state machine 120 of control unit 29 of chip 103 controls detailed operations of chip 103 such as the various individual steps necessary for carrying out programming, reading, and erasing operations. State machine 120 thus functions to reduce the overhead required of a processor (not depicted) typically used in association with chip 103.
Memory operations, including programming, reading, and erasing can be initiated in various ways. For all operations, the chip enable signal CE must be made active. To perform a read operation, write enable signal WE must be made inactive. For a write operation, signal WE must be made active. In order to reduce the likelihood of accidental modification of data, erase and program operations require receipt of two consecutive commands that are processed by command execution logic unit 124. The program and erase commands are provided by the associated processor to data I/O pins DQ0-DQ7, forwarded to input buffer 122, and then forwarded to the command execution logic unit 124 for processing.
If memory array 16 is to be erased (typically, all or large blocks of cells are erased at the same time), the processor causes the Output Enable OE pin to be inactive, and the Chip Enable CE and Write Enable WE pins to be active. The processor then issues an 8 bit command 20H (0010 0000) on data I/O pins DQ0-DQ7, typically called an Erase Setup command. This is followed by issuance of a second eight bit command D0H (1101 0000), typically called an Erase Confirm command. Two separate commands are used to reduce the possibility of an inadvertent erase operation.
The commands are transferred to data input buffer 122, and the commands are then transferred to command execution logic unit 124 of control unit 29. Logic unit 124 then instructs state machine 120 to perform all the numerous and well known steps for erasing array 16.
Once an erase sequence is completed, state machine 120 updates an 8 bit status register 126, the contents of which are transferred to data output buffer 128A which is connected to data I/O pins DQ0-DQ7 of the memory system. The processor periodically polls the data I/O pins to read the contents of status register 126 in order to determine whether an erase sequence has been completed and whether it has been completed successfully.
During a typical erase operation, it is desired to erase all the cells of array 16 (or an erase block of the cells) so that the threshold voltages are all within a specified voltage range. That range is typically a small positive voltage range such as from +1.5 to +3.0 volts. If the erased cells fall within this range, the cell to be read (the "selected" or "target") cell will produce a cell current in a read operation. The presence of cell current flow indicates that the cell is in an erased state (logic "1") rather than a programmed state (logic "0"). An example of a flash memory array which can be employed as memory array 16 of chip 103 is described in U.S. patent application Ser. No. 08/606,246, now U.S. Pat. No. 5,673,224 issued Sep. 30, 1997, entitled "Segmented Non-Volatile Memory Array with Multiple Sources with Improved Word Line Control Circuitry," and assigned to the assignee of the present application, the specification of which is incorporated herein by reference.
The present invention is useful as an improvement to flash memory systems, such as those of the type designed to emulate magnetic disk drive systems. This type of flash memory system is typically implemented as a card (for insertion into a computer system) with a chip set mounted thereon, where the chip set includes an onboard controller and several memory chips controlled by the controller. Each memory chip implements an array of flash memory cells organized into independently erasable blocks. A conventional flash memory system of this type can be modified in accordance with the invention to reduce the average time required to write packets of data bits (received from an external source) to the flash memory array.
In the past, magnetic hard disk systems have been the dominant storage media for computers and related systems. The support of magnetic disk systems is evident by the software associated with the disk drives. The dominant computer operating system known as "DOS" (Disk Operating System) is essentially a software package used to manage a disk system. DOS has been developed by IBM Corporation, Microsoft Corporation, and Novell as the heart of widely used computer software. The first generation of Microsoft Corporation's "Windows" operating system software was essentially a continuation of the original DOS software with a user friendly shell added for ease of use.
The DOS software was developed to support the physical characteristics of hard drive structures, supporting file structures based on heads, cylinders and sectors. The DOS software stores and retrieves data based on these physical attributes. Magnetic hard disk drives operate by storing polarities on magnetic material. This material is able to be rewritten quickly and as often as desired. These characteristics has allowed DOS to develop a file structure that stores files at a given location which is updated by a rewrite of that location as information is changed. Essentially all locations in DOS are viewed as fixed and do not change over the life of the disk drive being used therewith, and are easily updated by rewrites of the smallest supported block of this structure. A sector (of a magnetic disk drive) is the smallest unit of storage that the DOS operating system will support. In particular, a sector has come to mean 512 bytes of information for DOS and most other operating systems in existence. DOS also uses clusters as a storage unit. Clusters, however, are nothing more than the logical grouping of sectors to form a more efficient way of storing files and tracking them with less overhead.
The development of flash memory integrated circuits has enabled a new technology to offer competition to magnetic hard drives and offer advantages and capabilities that are hard to support by disk drive characteristics and features. The low power, high ruggedness, and small sizes offered by a solid state flash memory system make such a flash memory system attractive and able to compete with a magnetic hard disk drive system. Although a memory implemented with flash memory technology may be more costly than a hard disk drive system, computers and other processing systems are being developed that require (or benefit greatly from) use of flash memory features.
Thus, flash memory systems have been developed that emulate the storage characteristics of hard disk drives. Such a flash memory system is preferably structured to support storage in 512 byte blocks along with additional storage for overhead associated with mass storage, such as ECC (error correction code) bits. A key to this development is to make the flash memory array respond to a host processor in a manner that looks like a disk so the operating system can store and retrieve data in a known manner and be easily integrated into a computer system including the host processor.
In some flash memory systems that emulate the storage characteristics of hard disk drives, the interface to the flash memory is identical to a conventional interface to a conventional magnetic hard disk drive. This approach has been adopted by the PCMCIA standardization committee, which has promulgated a standard for supporting flash memory systems with a hard disk drive protocol. A flash memory card (including one or more flash memory array chips) whose interface meets this standard can be plugged into a host system having a standard DOS operating system with a PCMCIA-ATA (or standard ATA) interface. Such a flash memory card is designed to match the latter standard interface, but must include an onboard controller which manages each flash memory array independent of the host system. We next describe a typical technique for storing sectors or files of data in a flash memory array having the structure shown in FIG. 2. This structure may be suitable for low cost applications of the type commonly implemented using low cost magnetic disk drives. Flash memory array 116 of FIG. 2 has 544 bytes per row of flash memory cells (each byte consisting of eight bits, where each memory cell is capable of storing one bit). Thus, each row of cells is equivalent to a magnetic disk sector (512 bytes of data plus 32 bytes of "overhead").
Memory array 116 of FIG. 2 is partitioned into large "decode" blocks of cells (e.g., eight large decode blocks as shown in FIG. 2 or ten large decode blocks) that are physically isolated from one another. This partitioning of blocks allows defects in one decode block (e.g., decode block 16A) to be isolated from the other decode blocks in the array, allows defective decode blocks to be bypassed by a controller, and allows for high usage of die and enhances overall yield of silicon produced (driving down the cost of flash mass storage systems).
Each decode block is subdivided into a number of independently erasable blocks (e.g., eight "erase" blocks as shown in FIG. 2), sometimes referred to herein as "erase blocks." In the FIG. 2 example, each erase block (e.g., erase block 16B) consists of rows of flash memory cells, with each row being capable of storing seventeen "packets" of binary bits, and each packet consisting of 32 bytes (each byte consisting of eight binary bits). Thus, each row (capable of storing 544 byte) corresponds to one conventional disk sector (comprising 544 bytes), and each row can store 512 bytes of data of interest as well as 32 ECC bytes for use in error detection and correction (or 32 "overhead" bits of some type other than ECC bits). In the FIG. 2 example, each erase block corresponds to two "cylinders" of data (in the sense that this expression is used in a conventional magnetic disk drive), with each cylinder consisting of 256K bits of data organized into 64 sectors. Thus, each erase block in the FIG. 2 example consists of 128 sectors of data.
Still with reference to FIG. 2, each erase block (e.g., erase block 16B) can be independently erased in response to signals from the controller. All flash memory cells in each erase block are erased at the same (or substantially the same) time, so that erasure of an erase block amounts to erasure of a large portion of array 116 at a single time.
Stored data can be read from typical flash memories at higher speeds than from typical existing disk drives, since a flash memory system does not have mechanical delays such as seeks and rotational delays that are required for drive operation. This capability makes flash memories particularly useful in applications where read access is very important to users (e.g., it may be desirable to use a flash memory system as a cache to a traditional disk system).
However, conventional flash memory systems have slow write rates compared to those of DRAMS and SRAMS (and even disk drives in some applications). The programming mechanism for capturing charge in the floating gate of a cell of a flash array (in order to store a bit in such cell) is slow compared to the mechanism required to store a bit of data using these other technologies. While the write rate is often slower for conventional flash memories than it is for disk drives, in many cases a flash memory system will operate faster than a disk drive for storing data. This can occur because a flash memory does not have mechanical delays for moving a magnetic head to a desired storage location as are inherent in a disk drive before starting a write operation. Often, a flash memory system (of the type which emulates a disk drive) will be able to receive data and store it in a flash memory array in less time than required for the actuator of a hard disk drive to move to a desired storage location on a disk. However, as the length of a file being stored (the amount of data being stored) increases, this initial advantage of flash technology over disk technology will be overcome, and the faster-writing hard disk will catch up and surpass the flash memory (e.g., the disk will require less total time to store a sufficiently long file of data).
It would be desirable to improve existing technology for writing data to a flash memory array to allow storage of data (even large volumes of data, e.g., long files of data) more rapidly. One method of doing so would be to store data in wide words, where many bits are written at one time (each bit to a different cell of a flash memory array). While this would help speed up the write process it will demand more power of the flash system.
The high voltage required to program flash memory cells has traditionally been generated (or partially generated and regulated) internal to the flash memory device. The lack of inductors or the ability to include large capacitors in a solid state flash design limits the amount of charge that can be generated and stored on a flash memory chip. To program more and more bits during a single short-duration operation requires more power and has heavier demands on the on-chip "pump" circuitry for supplying high power to the flash memory cells. As the demand for power from the pump circuitry increases, each particular implementation of the pump circuitry will reach its limit and will begin to droop in its output power, reducing the efficiency of the programming operation, even to the point of causing programming failure if loaded heavily.
The present invention provides a way to write many data bits (a long packet of data) during a short-duration operation to many flash memory cells, with substantially reduced power consumption relative to the prior art.
Another problem addressed by the present invention pertains to the statistical effect of programming large numbers of bits simultaneously. Due to differences in the characteristics of cells in a single flash array (e.g., due to the manufacturing tolerances), the bits of a group of bits being programmed in parallel (to a corresponding number of flash memory cells) will not all program at the same rate, so that the rate of programming the group of bits is governed the slowest bit in that group to achieve the programmed state. This difference in speeds will cause nearly all bits being programmed within a group to see longer program conditions than if each were being programmed alone. This extended programming will cause additional stress on cells of a flash memory array and is a contributor to premature cell wear out (reduced operating lifetime).
Another problem addressed by the present invention pertains to the total time required to write large numbers of bits sequentially (during a single write operation) to erased flash memory cells. The average total time required to write the bits of an X-bit group of bits (where X is a large number and the average is over a number of writes of the group, assuming random values of the bits of during each write) sequentially to a corresponding number of flash memory cells will depend on the average value of the bits. Thus, if the bits are binary bits, and they are written to erased flash memory cells (each erased cell indicative of the value "1"), a greater time is needed to write the bits to the cells when the bits are entirely (or mostly) "0" bits than when the bits are entirely (or mostly) "1" bits.
In addition to reducing power requirements for writing many bits simultaneously (or as part of a single short-duration operation), the present invention reduces the average time for writing X-bit packets of bits to a flash memory array (for any given value of X), and increases the average operating lifetime of the array's cells (where two or more streams of the bits are written in parallel to the cells). This is true since the invention reduces (to a number less than X) the average number of cells that must be programmed to accomplish writing of X-bit packets of data to a flash memory (where the average is over a number of writes of such packets, assuming random values of the bits of each packet).
A flash memory system consumes less power when a bit having a first logical value is written to a cell thereof than when a bit having another logical value is written to an erased cell. In particular, where each cell is indicative of a binary data bit, and the cell is indicative of a bit having a first logical value, a substantial amount of power is required to program the cell (to cause it to change state to become indicative of a bit having a second logical value), but no power is required to "write" a bit having the first logical value to the erased cell.
Typically (in cases in which each cell of a flash memory array is indicative of a binary data bit), the logical value of the data bit indicated by an erased flash memory cell is considered to be the logical value "1," and the logical value of the binary data bit indicated by a programmed flash memory cell is considered to be the logical value "0."
A typical implementation of a flash memory array comprises rows and columns of flash memory cells, with each row consisting of cells connected along a common wordline, and each column consisting of cells connected along a common bitline. Each cell is implemented by a floating-gate N-channel transistor. The drains of each column of such transistors are connected to a common bitline, the gate of each is connected to a different wordline, and the source of each is held at a source potential (which is usually ground potential for flash memory chip during a program or read operation). Each cell is a nonvolatile memory cell, since it has a floating gate capable of semipermanent charge storage. The current drawn by each cell depends on the amount of charge stored on the cell's floating gate. Thus, the charge stored on each floating gate determines a data value that is stored semipermanently in the corresponding cell. The charge stored on the floating gate of each cell can be reduced (and thus the data value stored by each cell is erasable) by appropriately changing the voltage applied to the gate and source in a well known manner. Conventionally, the logical value of a binary data bit indicated by an erased flash memory cell of this type (which has charge below a particular level on its floating gate) is considered to be the logical value "1," and the logical value of a binary data bit indicated by a programmed flash memory cell of this type (which has charge above a particular level on its floating gate) is considered to be the logical value "0."
It has been proposed to "level" (i.e., make more uniform) the erasure/programming history of sectors of cells of an electrically erasable programmable read only memory (EEPROM), such as a flash EEPROM, by sequentially (or randomly) inverting the polarity of sets of binary data sequentially written to each sector of the cells. For example, U.S. Pat. No. 5,396,468 (issued Mar. 7, 1995) and U.S. Pat. No. 5,369,615 (issued Nov. 29, 1994) teach inverting the polarity of sets of binary data to be written to a sector of cells of an EEPROM as follows. A set of data (indicative of multiple bits of binary data) is written to the sector, then the polarity of the next set to be written to the sector is automatically inverted (each bit indicative of a logical "1" is replaced by a bit indicative of a logical "0" and vice versa) and the resulting set of inverted bits is written to the sector, then the next set of data is written to the sector without being inverted, and so on. The references also teach inverting the polarity of successive sets (to be written to a sector) on a random basis, as an alternative to inverting the polarity of every other set to be written.
However, such predetermined alternating (or random) polarity inversion of sets of data bits to be written to an EEPROM is very different from selective inversion of the polarity of a packet of data in accordance with the present invention (in response to determining the number of bits of the packet which are indicative of a particular logical value), and would not achieve the advantages achieved by the present invention. In particular, predetermined alternating (or random) polarity inversion of packets would neither reduce the average power consumption required to write the packets to a flash memory (averaged over many writes of packets, assuming random values of the bits of each packet), nor would it reduce the average time for writing each packet to the flash memory (again averaged over many writes of packets, assuming random values of the bits of each packet).
It has also been proposed (in European Patent Application Publication Number 444,774 A2, published on Sep. 4, 1991) to employ logic circuitry (of an unspecified type) to count the number of bits of an N-bit data word (to be written to a memory) which are indicative of a logical "zero," to invert the polarity of the N-bit word if it comprises more bits indicative of a logical "zero" than bits indicative of a logical "one" (or not invert the word's polarity if the word comprises more bits indicative of a logical "one" than bits indicative of a logical "zero"), and to write the encoded (inverted or not inverted) word to the memory with a bit identifying whether or not the encoded word has been inverted. However, it would not be practical to implement this technique in cases in which N is a large number (e.g., where N is much greater than eight). In contrast, in accordance with preferred embodiments of the invention, a set of data (consisting of N binary bits) is processed on a packet-by-packet basis (preferably in a particularly efficient manner, using a converter and circuitry for accumulating a sequence of outputs of the converter) to encode each packet selectively in response to determining whether more than (or less than) half of the bits of each packet are indicative of a first binary level (a logical "one" or "zero"), where each packet consists of X of the binary bits in the set, and the set consists of more than X of the binary bits.